六省联考2017 乱写
寿司餐厅
$mx^2 + cx$ 解读：吃一个 $x$ 代价 $x$，吃过 $x$ 代价 $mx^2$
看题：
如果选了 $d_{i, j}$，则必须选择 $d_{l, r} (i \leq l \leq r \leq j)$，必须选择 $d_{k, k} ( i \leq k \leq r )$
可以在 $d_{k, k}$ 处减去代价 $a_k$
选了 $d_{k, k}$ 就必须选择物品 $a_k$，代价 $m * a_k^2$
至此已经转化为最大权闭合子图模型。
关于建图：怎么选所有子区间？从 $d_{i, j}$ 向 $d_{i + 1, j}$ 和 $d_{i, j - 1}$ 连 $\infty$ 边表示强制选。
期末考试
大水桶题，枚举最晚时间，前后缀算一算。卡 long long，从小到大枚举最晚时间，如果仅仅是同学的不满意度已经大于历史的 $ans$ 最小值就 break。
组合数问题
组合意义（这个真的不阴间）：从 $nk$ 个物品中选 $t (t \mod k = r)$ 个物品的方案数。
朴素 dp：$f_{i, j}$ 表示到第 $i$ 个物品，选的物品个数 $\mod k = j$ 的方案数。转移就是循环的形式。
注意到 $K$ 和 $r$ 很小，矩乘即可。
另一种做法：$\sum\limits_{i \mod k = r} \binom{nk}{i} = \sum\limits_{i \mod k = r} [x^i] (1 + x)^{nk}$，暴力做多项式快速幂取模即可。
摧毁树状图
暴力拼起来有 84！考场上谁 tm 去写正解啊
只有两种情况：相交与不相交。
设计状态的时候考虑两条路径“生长”的过程。状态如下：
- $dp_{x, 0}$：选一条上端点为 $x$ 的路径的最大连通块数
- $dp_{x, 1}$：选一条 $x$ 子树里不经过 $x$ 的路径的最大连通块数（注意这时 $x$ 和 $x$ 的父亲会构成新连通块）
- $dp_{x, 2}$：选一条 $x$ 子树里经过 $x$ 的路径的最大连通块数
- $dp_{x, 3}$：选一条上端点为 $x$ 的路径，和一条 $x$ 子树里的路径（两者边不相交）的最大连通块数
注意：这里的最大连通块数都仅指「$x$ 子树内」。
转移比较常规，细节有点多，建议看代码：点我
分手是祝愿
首先按键的方案唯一——从后往前就能唯一确定。$50$ 分就直接从后往前按。
考虑正解：除开这些必须按的键，如果按了其他的键 就得按同一个键按回来。
根据期望线性性，将 dp 状态设为 $f[i]$ 表示从 $i$ 个必选的键转移到 $i - 1$ 个必选的键的期望操作次数。
第一项表示选了一个必选的，一次就到 $i - 1$ 去了；第二项表示选了一个其他的，就得 $f[i + 1]$ 次按回来，再 $f[i]$ 次按到 $i - 1$ 去。解一个一元一次方程就好了（
很神仙！
相逢是问候
就剩一道了！加油 xml！
做过的套路题，套了数论皮子的暴力题。
扩展欧拉定理：$a ^ b \mod{p} =$
$b < \varphi(p)$：$a^{b}$
$b \geq \varphi(p)$：$a^{b \% \varphi(p) + \varphi(p)}$
这题本质是个套娃，$c^{c^{c^{\cdots}}} \mod{p} = c^{c^{c^{\cdots}} \mod{ \varphi(p) } + \varphi(p)（加不加 \varphi(p) 要按上面那样分类讨论） } \mod{p}$，一直套娃下去，模数变成 $\varphi(\varphi(\varphi(\cdots\varphi(p)))) = 1$，并且只要 $log$ 层。
所以像 segment tree beats 那样维护线段树每个区间最小修改次数，如果超过 $log$ 就不改了因为值再也不会变了，否则就递归下去。复杂度三只 $log$：线段树一只，扩展欧拉定理一只，快速幂一只，而快速幂那只可以预处理优化掉所以最后是两只 $log$。
总结：「寿司餐厅」如果再熟练一些就能自己做出来了……感觉对模型的转化还不够。待会去做 CF 题「摧毁树状图」恶心人的树形 dp，口区口区。「分手是祝愿」还是挺有意思的，我喜欢它！